package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.*;

/**
 * 图问题, 拓扑排序, 其实就是广搜
 *
 * @author tzp
 * @since 2020/10/19
 */
public class LC207_1 implements TreeProblem, GraphProblem {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> links = new HashMap<>();
        int[] degree = new int[numCourses];
        for (int[] pres : prerequisites) {
            //to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
            //拓扑排序, 看做 1 -> 0, 1完了之后才能做0, 统计入度
            links.compute(pres[1],
                    (key, oldValue) -> {
                        if (oldValue == null) oldValue = new ArrayList<>();
                        oldValue.add(pres[0]);
                        return oldValue;
                    }
            );
            degree[pres[0]]++;
        }

        LinkedList<Integer> queue = new LinkedList<>();//可达的课程的队列
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) queue.offerLast(i);//初始入度为0的课程全加进去, 其实就是先把广搜的根节点
        }
        int count = 0;
        while (queue.size() > 0) {
            Integer course = queue.pollFirst();//自己走了,
            count++;
            if (links.containsKey(course)) {
                for (Integer next : links.get(course)) {//把自己的所有next的入度减一
                    degree[next] = degree[next] - 1;
                    if (degree[next] == 0) queue.offerLast(next);
                }
            }
        }
        return count == numCourses;
    }

    //numCourses = 2, prerequisites = [[1,0]]
    public static void main(String[] args) {
        System.out.println(new LC207_1().canFinish(3, new int[][]{{0, 1}, {2, 1}}));
        System.out.println(new LC207_1().canFinish(3, new int[][]{{0, 1}, {1, 0}}));
    }
}
